//
//  SString.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/7/23.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef SString_hpp
#define SString_hpp

#include <stdio.h>
#include <iostream>

#define MAXLEN 255

// 为了方便获取位置，ch[0]不存储数据，从ch[1]开始存储
// int length保存字符串长度
typedef struct {
    char ch[MAXLEN];
    int length;
} SString;

// 赋值操作
void StrAssign(SString &T, char *chars);

// *求子串*
bool SubString(SString &Sub, SString S, int pos, int len);

// *比较字符串大小*
int StrCompare(SString S, SString T);

// **定位操作** 找到S中T子串的位置，如不存在则返回0
int Index(SString S, SString T);

// **朴素定位操作**
int BFIndex(SString S, SString T);

// *** KMP算法模式匹配 ***
int Index_KMP(SString S, SString T, int next[]);

// ***** KMP获取next数组 *****
// 模式串的子串部分匹配时，KMP算法效率才高。否则和朴素算法差不多
// 第j个字符匹配失败时，前1～j-1个字符组成的子串计为S
// next[j] = S的最长的相同的前缀和后缀长度+1
// 特别的next[1] = 0
// 'ababaa'     'aaaab'
// 1 2 3 4 5 6  1 2 3 4 5
// 0 1 1 2 3 4  0 1 2 3 4
// ‘google’
// 1 2 3 4 5 6
// 0 1 1 1 2 1


// ***** KPM算法优化 *****
// 从next数组求nextval
// a a a a b
// 1 2 3 4 5
// 0 1 2 3 4
// 0 0 0 0 0

/*
 总结
 串的定义：数组存字符，int存长度
 获取子串：开始位置+子串长度+遍历
 比较串：比大小+比长度
 朴素定位：双指针简单二重遍历（暴力法O(MN)）
 KMP：双指针利用next遍历 O(N)
 next数组：最长相同前后缀+1 O(m)
 nextval数组：字符相同，指针相同
 */
#endif /* SString_hpp */
